/* 无重复的子字符串
    给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
    示例 1:
    输入: s = "abab"
    输出: true
    解释: 可由子串 "ab" 重复两次构成。

    示例 2:
    输入: s = "aba"
    输出: false

    示例 3:
    输入: s = "abcabcabcabc"
    输出: true
    解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。) 
*/
#include <iostream>
#include <string>

using namespace std;

// 判断能否由字串构成
bool repeatedSubstringPattern(string s)
{
    int n = s.size();
    // 外循环：遍历可能字串的长度
    for (int len = 1; len <= n / 2; len++)
    {
        // 如果能整除，才有可能由重复子串组成
        if (n % len == 0)
        {
            bool isMatch = true;
            // 内循环：比较相隔len的字符是否相等（类比于滑动窗口）
            for (int i = len; i < n; i++)
            {
                if (s[i] != s[i - len])
                {
                    isMatch = false;
                    break;
                }
            }
            if (isMatch)
            {
                return true;
            } 
        }
    }
    return false;
}

int main()
{
    int result = repeatedSubstringPattern("aabaabaab");
    cout << result << endl;
    return 0;
}
